package test.tongcheng;

import java.util.Scanner;

/**
 * @description: 同程旅行：20单选 + 2编程
 * @author: w_jingbo
 * @date: 2023/9/14
 * @Copyright: 博客：http://coisini.wang
 */
public class Main {

    public static void main(String[] args) {
        int[] arr = new int[] {8,6,1,12,7} ;
        quickSort(arr);
        for (int i : arr) {
            System.out.println(i);
        }

    }

    public static int[] quickSort (int[] arr) {
        // write code here
        sort(arr,0,arr.length-1);
        return arr;
    }

    public static void sort(int[] arr , int left , int right ){
        if(left < right){
            int index = paration(arr,left,right);
            sort(arr,left,index-1);
            sort(arr,index+1,right);
        }
    }

    public static int paration(int[] arr , int left , int right){
        int p = arr[right] ;
        int i = left  ;
        for(int j = left ; j < right ; j++){
            if(arr[i] < p){
                i++;
                swap(arr,i,j);
            }
        }
        return i;
    }

    public static void swap(int[] arr , int i , int j){
        int tmp = arr[i];
        arr[i] = arr[j] ;
        arr[j] = tmp ;

    }
}


/*

int[][] envelopes = new int[][]{{1,2},{1,1},{3,3},{3,4}} ;
        int m = envelopes.length ;
        int n = envelopes[0].length ;
        int mMax = 0 ;
        int nMax = 0 ;
        int res = 1 ;
        for (int i = 0; i < m; i++) {
            int count = 1 ;
            mMax = envelopes[i][0] ;
            nMax = envelopes[i][1] ;
            for (int j = 0; j < m; j++) {
                if(mMax > envelopes[j][0] && nMax > envelopes[j][1]){
                    count++;
                }
            }
            res = Math.max(count,res) ;
        }
        System.out.println(res);
 */
